package com.itheima.algorithm.divideandconquer;

import java.util.concurrent.ThreadLocalRandom;

/**
 * <h3>快速选择算法 - 分而治之</h3>
 */
public class QuickSelect {

    /*
        求排在第 i 名的元素，i 从 0 开始，由小到大排
        6   5   1   2   4


     */
    static int quick(int[] array, int left, int right, int i) {
        /*
            0   1   2   3   4
            1   2   4   5   6
         */
//        Arrays.sort(array); // n*log(n) 时间复杂度太高
//        return array[i];
        int p = partition(array, left, right); // 基准点元素索引值
        if (i == p) {
            return array[i];
        }
        // 快速选择算法时间复杂度 0(n)
        if (i < p) {
            return quick(array, left, p - 1, i);
        } else {
            return quick(array, p + 1, right, i);
        }
    }

    /*
        注意事项
        1. 为啥要加内层循环的 i<j 条件
        2. 为啥要先处理 j，再处理 i
        3. 随机元素作为基准点
        4. 如果有大量重复元素
     */
    private static int partition(int[] a, int left, int right) {
        int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
        // [0~9] right-left+1=3 [0,2]+4=[4,6]
        swap(a, idx, left);
        int pv = a[left];
        int i = left;
        int j = right;
        while (i < j) {
            // 1. j 从右向左找小(等)的
            while (i < j && a[j] > pv) {
                j--;
            }
            // 2. i 从左向右找大的
            while (i < j && a[i] <= pv) {
                i++;
            }
            // 3. 交换位置
            swap(a, i, j);
        }
        swap(a, left, i);
        return i;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        int[] array = {6, 5, 1, 2, 4};
        System.out.println(quick(array, 0, array.length - 1, 0));
        System.out.println(quick(array, 0, array.length - 1, 1));
        System.out.println(quick(array, 0, array.length - 1, 2));
        System.out.println(quick(array, 0, array.length - 1, 3));
        System.out.println(quick(array, 0, array.length - 1, 4));
    }
}
